import numpy as np
#打开文件
with open("Floyd.txt", "r") as f:  # 打开文件
    data = f.read()  # 读取文件
datalist=data.replace("\n"," ")
datalist=datalist.split(" ")
#获取n和m
n=int(datalist[0])
m=int(datalist[1])
datalist.pop(0)#用完出栈,方便处理
datalist.pop(0)

# 初始化
matrix=[[np.inf for col in range(n)] for row in range(n)]#初始化n*n矩阵所有点点距离为无穷
for i in range(n):
  matrix[i][i]=0#自己到自己为0

#读取序偶序列存入列表
datalist=[datalist[i:i + 3] for i in range(0, len(datalist), n)]
#更新邻接矩阵
for i in range(len(datalist)):
  if datalist[i][0] is not '':
    x=int(datalist[i][0])#元组第一项为x
    y=int(datalist[i][1])#元组第二项为y
    weight=int(datalist[i][2])#权值为第三项
    matrix[x-1][y-1]=weight#更新权值
    matrix[y-1][x-1]=weight

#Floyd算法
for k in range(n):
    for i in range(n):
        for j in range(n):
            if (matrix[i][k]+matrix[k][j]) < matrix[i][j]:
                matrix[i][j] = matrix[i][k]+matrix[k][j]


print(matrix)

#写入文件
f = open('Floyd_Ans.txt', 'w')
for i in range(n):
  f.writelines(str(matrix[i]))
  f.write('\n')
f.close()
